Conventionally, for a Reed-Solomon decoding circuit, there is known a method of sequentially processing input signals by a systolic array structure as disclosed in a literature “VLSI-oriented Reed Solomon Coding and Decoding System”, Journal of the Society of Electronic Information Communication, Vol. J. 71-A, pp. 751 to 759.
In the system disclosed in the above literature, a unit structure termed PE, shown in FIG. 5, is used for processing. Referring to FIG. 5, seven signals A, B, C, D, E, I and J are entered as input signals, of which the signals A, B, D and E are sent to a selector 501, that is also fed with control signals S1 and S2. A first output of the selector 501 is sent to a second D-flipflop (D-F/F) 508, while a second output thereof is branched into three which are entered to a first input of a first Galois field multiplication circuit 502 and to an input of the first D-flipflop 505 (D-F/F) and are output to an output G.
A third output of the selector 501 is branched into three which are entered to a first input of a second Galois field multiplication circuit 503 and to an input of the fifth D-flipflop 507 (D-F/F) and are output to an output H.
An input signal I is entered to a second input of the first Galois field multiplication circuit 502, while an input signal J is entered to a second input of the second Galois filed multiplication circuit 503.
An output of the first Galois filed multiplication circuit 502 is entered to a first input of an exclusive OR circuit 504, while an output of the second Galois filed multiplication circuit 503 is entered to a second input of the exclusive OR circuit 504.
Outputs of the first to fifth D-F/Fs 505, 508, 506, 509 and 507 are issued as outputs O, R, Q, T and P, respectively.
In the conventional example, a variety of processing operations is performed on the PE as a unit. A syndrome polynomial calculating unit, an Euclidean algorithm method, Chain solution and an error value calculation unit are implemented by interconnecting PEs.
The syndrome polynomial calculating unit is implemented by interconnecting (K+1) PEs in series, a to a(K+1). Also, C is fixed at “0”, J is fixed at “0” and an output of P of a previous stage PE is entered to B. In this case, a Q-output of the PE of the last stage becomes an output of the syndrome polynomial.
As for outputs of a selector, C and B are selected in the first PE as outputs of X and Y, respectively. In the following PEs, A and B are selected as X and Y, respectively.
In the Euclidean algorithm calculating unit, (K+2) PEs are connected in series, and outputs of respective previous stage(s) R, Q and T are entered to A, C and B of the next stage(s).
In the individual PEs, outputs of H and G are entered to a respective register which holds initially entered values. The register holds the value during calculation processing to enter the values to inputs I and J, respectively, as shown in FIG. 7.
Also, outputs O and P are sent to inputs D and E, respectively. In the initial stage PE, the calculated results of the syndrome polynomial are entered to A, while C is fixed at “0”, and “1” is entered only at the initial bit of B.
In the respective PEs, signals selected by the selectors are changed depending on the processing results of the previous stage(s). That is, for the respective PEs, the mode is changed to nop, reDuceA and reDuceB, depending on the order number of the output signals R, Q and T. In keeping therewith, A and B are selected for X and Y, respectively, in the downstream side selector in the case of nop. In the case of reDuceA, C and B are selected for X and Y, respectively, whereas, in the case of reDuceB, A and C are selected for X and Y, respectively.
This outputs an error position polynomial and an error value polynomial from R and Q of the last-stage PE, respectively.
In the downstream side, two PEs are configured as a reciprocal calculating circuit of the Galois field, as shown in FIG. 8. To I, J, A and B are entered polynomials calculated by the Euclidean algorithm method and differentiated values thereof. An output Q of the initial stage PE is sent to a Galois field reciprocal calculating circuit, an output of which is sent to an input B of the next stage PE. In this case, the signal of an output Q of the last stage PE serves as the information of the error position and the error value, by which the error values are corrected.